GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Neighbor-Joining-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Neighbor-Joining-Algorithmus</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>Neighbor-Joining-Algorithmus</b> ist ein mathematisches Verfahren, um Datensätze zu vergleichen und <a href="Hierarchie" title="Hierarchie">hierarchisch</a> <i>bifurcal</i> (zweigabelig) anzuordnen. Dieses Verfahren wurde 1987 von Saitou und Nei vorgestellt<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> und 1988 von Studier und Keppler weiterentwickelt und vereinfacht.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendung">Anwendung</h2></div>

<p>In der <a href="Bioinformatik" title="Bioinformatik">Bioinformatik</a> bezeichnet das Neighbor-Joining-Verfahren eine phänetische <a href="Top-down_und_Bottom-up" title="Top-down und Bottom-up">bottom-up</a> <a href="Clusteranalyse" title="Clusteranalyse">Clustermethode</a>, welche zur Erstellung von <a href="Phylogenese" title="Phylogenese">phylogenetischen</a> <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baumstrukturen</a> verwendet wird. Hiermit soll anhand von variierenden Merkmalen in der <a href="Datenmatrix" title="Datenmatrix">Datenmatrix</a> die Wahrscheinlichkeit einer Abstammungs- oder Verwandtschaftsbeziehung in einer <a href="Stammbaum" title="Stammbaum">stammbaumartigen</a> Darstellung berechnet werden.

</p><p>Normalerweise werden damit Bäume aus <a href="Desoxyribonukleins%C3%A4ure" title="Desoxyribonukleinsäure">DNA</a>- oder <a href="Protein" title="Protein">Proteinsequenzdaten</a> oder klassisch <a href="Morphologie_(Biologie)" title="Morphologie (Biologie)">morphologischen</a> Datensätzen erstellt. Der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> benötigt Wissen über die Distanz zwischen zwei Paaren von <a href="Taxon" title="Taxon">Taxa</a> (also beispielsweise Arten oder Sequenzen) in einem Baum.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithmus">Algorithmus</h2></div>

<p>Neighbor-joining basiert meist auf dem „Minimum Evolution“-Kriterium für phylogenetische Bäume: Ausgehend von einem zunächst sternförmigen „Baum“, in dem alle Taxa mit einem „Zentrum“ verbunden sind, werden paarweise die DNA- oder Proteinsequenzen mit der geringsten genetischen Distanz ausgewählt und zu einem Ast des Baumes vereinigt. Die genetischen Distanzen der Sequenzen werden neu berechnet und wieder die nächstverwandten zu einem Ast mit zwei Taxa zusammengefügt. Dies erfolgt solange, bis alle Taxa in dem Baum eingefügt wurden und die Sternstruktur des Baumes völlig aufgelöst wurde. Im Unterschied zum <a href="Unweighted_Pair_Group_Method_with_Arithmetic_mean" title="Unweighted Pair Group Method with Arithmetic mean">UPGMA</a> berücksichtigt <i>Neighbor-Joining</i>, dass die Evolutionsgeschwindigkeit nicht konstant ist: Wenn ein Taxon von allen anderen Taxa weit entfernt ist, so ist dies nicht auf einen entfernten Verwandtschaftsgrad, sondern auf beschleunigte Evolution zurückzuführen.

</p><p>Der Algorithmus ist <a href="Iteration" title="Iteration">iterativ</a> und ersetzt in jedem Schritt ein Paar der <a href="Taxon#OTU" title="Taxon">Operational Taxonomic Units (OTU)</a> durch eine neue Sequenz. Er iteriert auf den jeweils verbleibenden Sequenzen weiter, bis es für drei verbleibende OTUs nur noch eine mögliche <a href="Topologie_(Mathematik)" title="Topologie (Mathematik)">Topologie</a> gibt. Danach wird die Baumstruktur erstellt.<sup id="cite_ref-Algorithmus_2-0" class="reference"><a href="#cite_note-Algorithmus-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<p>Folgend ist eine typische Tabelle von Distanzen zwischen Taxa angegeben, wobei die Werte rein hypothetisch, aber realistisch sind:<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Studier und Keppler führten einen alternativen Parameter im Algorithmus ein, der als Mij bezeichnet wird. Saitou und Nei verwendeten ursprünglich zur Bestimmung der Nachbarn die „minimal sum of branches“ (Sij) also die minimale Anzahl an Verzweigungen. Das Beispiel basiert auf dem Algorithmus von Studier und Keppler, welche gegen den ursprünglichen Parameter eine <a href="Komplexit%C3%A4tsklasse" title="Komplexitätsklasse">Komplexitätsklasse</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6b04f5c5cfea38f43406d9442387ad28555e2609.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{3})}" loading="lazy"></span> bietet.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<th>

</th>

<th>Mensch

</th>

<th>Maus

</th>

<th>Rose

</th>

<th>Tulpe

</th></tr>

<tr>

<th>Mensch

</th>

<td>12

</td></tr>

<tr>

<th>Maus

</th>

<td>11

</td></tr>

<tr>

<th>Rose

</th>

<td>4

</td></tr>

<tr>

<th>Tulpe

</th>

<td>0

</td></tr></tbody></table>

<p>Da die Tabelle dreiecks-symmetrisch ist, muss die untere Hälfte nicht unbedingt gespeichert werden. Die Werte in dieser Tabelle werden als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{i,j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{i,j}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a483b0f56e8840318b5ae0afbb97f0d99e2effe0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.143ex; height:2.843ex;" alt="{\displaystyle d_{i,j}}" loading="lazy"></span> benannt.

</p><p><b>Schritt 1:</b> Es müssen die Durchschnittlichen Distanzen von jedem Taxon zu jedem anderen berechnet werden. Dies geschieht mit folgender Formel für die Netto-Divergenz r<sub>i</sub>:<sup id="cite_ref-Algorithmus_2-1" class="reference"><a href="#cite_note-Algorithmus-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i}={\frac {1}{N-2}}\sum _{k=1}^{N}d_{i,k}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{i}={\frac {1}{N-2}}\sum _{k=1}^{N}d_{i,k}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/faa2b9fc011c6d3ea9c991f85248d15b154ff864.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:19.301ex; height:7.343ex;" alt="{\displaystyle r_{i}={\frac {1}{N-2}}\sum _{k=1}^{N}d_{i,k}}" loading="lazy"></span>

</p><p>Wobei N die Anzahl der Taxa ist.

</p>

<th>Mensch

</th>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{1}={\frac {0+3+14+12}{4-2}}=14{,}5}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/812a397cd54924ae96c3f1ca02caadb356112269.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:28.766ex; height:5.343ex;" alt="{\displaystyle r_{1}={\frac {0+3+14+12}{4-2}}=14{,}5}" loading="lazy"></span>

</td></tr>

<tr>

<th>Maus

</th>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{2}={\frac {3+0+13+11}{4-2}}=13{,}5}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b9f8edce7d96fc01f8d58dd2c88cb638a0c8b36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:28.766ex; height:5.343ex;" alt="{\displaystyle r_{2}={\frac {3+0+13+11}{4-2}}=13{,}5}" loading="lazy"></span>

</td></tr>

<tr>

<th>Rose

</th>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{3}={\frac {14+13+0+4}{4-2}}=15{,}5}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91e172b2b1e15afe6a888c0f240006ec4e871433.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:28.766ex; height:5.343ex;" alt="{\displaystyle r_{3}={\frac {14+13+0+4}{4-2}}=15{,}5}" loading="lazy"></span>

</td></tr>

<tr>

<th>Tulpe

</th>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{4}={\frac {12+11+4+0}{4-2}}=13{,}5}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/016333c584391d41ed0f63f914dfe1eef492a812.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:28.766ex; height:5.343ex;" alt="{\displaystyle r_{4}={\frac {12+11+4+0}{4-2}}=13{,}5}" loading="lazy"></span>

</td></tr></tbody></table>

<p>Interpretation: Die Rose besitzt in unserem Beispiel die größte Netto-Divergenz, hat also im Vergleich mit den anderen Taxa eine größere Evolutionsgeschwindigkeit durchlebt.

</p><p><b>Schritt 2:</b> Wir berechnen eine Zwischenmatrix M.

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{i,j}=d_{i,j}-(r_{i}+r_{j})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i,j}=d_{i,j}-(r_{i}+r_{j})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c654425fc585160448259a4bbaf15b39ecfe06ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.727ex; height:3.009ex;" alt="{\displaystyle M_{i,j}=d_{i,j}-(r_{i}+r_{j})}" loading="lazy"></span>

</p><p>Wie z. B. zwischen Mensch und Maus:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{1,2}=d_{1,2}-(r_{1}+r_{2})=3-(14{,}5+13{,}5)=-25}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{1,2}=d_{1,2}-(r_{1}+r_{2})=3-(14{,}5+13{,}5)=-25}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fba385b3c2d8c0f2ddd32d697926c23ce67cea2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:50.175ex; height:3.009ex;" alt="{\displaystyle M_{1,2}=d_{1,2}-(r_{1}+r_{2})=3-(14{,}5+13{,}5)=-25}" loading="lazy"></span>

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span>

</th>

<th>Mensch

</th>

<th>Maus

</th>

<th>Rose

</th>

<th>Tulpe

</th></tr>

<tr>

<th>Mensch

</th>

<td>−16

</td></tr>

<tr>

<th>Maus

</th>

<td>−16

</td></tr>

<tr>

<th>Rose

</th>

<td>−25

</td></tr>

<tr>

<th>Tulpe

</th>

<td>

</td></tr></tbody></table>

<p><b>Schritt 3:</b> In dieser neu berechneten <a href="Distanzmatrix" title="Distanzmatrix">Distanzmatrix</a> M wird nun der kleinste Wert, also die kleinste Distanz zwischen zwei Taxa, gesucht, und die gefundenen zwei Taxa werden zu einem neuen Teilbaum u = (i,j) zusammengefügt. In diesem Beispiel ergeben sich also die zwei Möglichkeiten Mensch und Maus, oder Rose und Tulpe zu einem Teilbaum zusammenzufügen. Wir entscheiden uns zunächst für Mensch und Maus.

</p><p>Die Kantenlänge des Knotens zu der Verzweigung berechnet sich wie folgt:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i,u}={\frac {d_{i,j}+r_{i}-r_{j}}{2}}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i,u}={\frac {d_{i,j}+r_{i}-r_{j}}{2}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a08bd41ac22a1dde8342cefb578c1a09cc348576.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:19.89ex; height:5.676ex;" alt="{\displaystyle v_{i,u}={\frac {d_{i,j}+r_{i}-r_{j}}{2}}}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j,u}=d_{i,j}-v_{i,u}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j,u}=d_{i,j}-v_{i,u}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/38055d0d8b2258b1bab09cd596816d6c29688ba9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.842ex; height:2.843ex;" alt="{\displaystyle v_{j,u}=d_{i,j}-v_{i,u}}" loading="lazy"></span>

</p><p>Also Mensch zu MeMa ist gleich <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {3+14,5-13,5}{2}}=2}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {3+14,5-13,5}{2}}=2}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2124ce0a8afce8e7d8fb99043c569dd0e6745756.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:20.983ex; height:5.343ex;" alt="{\displaystyle {\frac {3+14,5-13,5}{2}}=2}" loading="lazy"></span>

</p><p><b>Schritt 4:</b> In der ursprünglichen Distanzmatrix wird der neue Eintrag u = MeMa angefügt:

</p>

<th>

</th>

<th>Mensch

</th>

<th>Maus

</th>

<th>Rose

</th>

<th>Tulpe

</th>

<th>MeMa

</th></tr>

<tr>

<th>Mensch

</th>

<td>?

</td></tr>

<tr>

<th>Maus

</th>

<td>?

</td></tr>

<tr>

<th>Rose

</th>

<td>?

</td></tr>

<tr>

<th>Tulpe

</th>

<td>?

</td></tr>

<tr>

<th>MeMa

</th>

<td>0

</td></tr></tbody></table>

<p>Um die Distanzen des neuen Eintrages u = (i,j) = (1,2) = (Mensch, Maus) = MeMa zu den restlichen Taxa zu berechnen, wird folgende Formel verwendet:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{u,k}={\frac {d_{i,k}+d_{j,k}-d_{i,j}}{2}}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{u,k}={\frac {d_{i,k}+d_{j,k}-d_{i,j}}{2}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c8036ed327c7cb35af732cfc0d1b304a57b29bfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:23.209ex; height:5.676ex;" alt="{\displaystyle d_{u,k}={\frac {d_{i,k}+d_{j,k}-d_{i,j}}{2}}}" loading="lazy"></span>

</p><p>Wobei die Einträge i und j zu einem neuen Eintrag u zusammengefügt wird, und die Distanz zum Eintrag k ausgerechnet wird. Die Distanz zwischen Rose und dem neuen Teilbaum ist also:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{5,3}={\frac {d_{1,3}+d_{2,3}-d_{1,2}}{2}}={\frac {14+13-3}{2}}=12}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{5,3}={\frac {d_{1,3}+d_{2,3}-d_{1,2}}{2}}={\frac {14+13-3}{2}}=12}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/562a9892fd958187a01f507a7b4ee07be4a94010.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:44.636ex; height:5.509ex;" alt="{\displaystyle d_{5,3}={\frac {d_{1,3}+d_{2,3}-d_{1,2}}{2}}={\frac {14+13-3}{2}}=12}" loading="lazy"></span>

</p><p>Die „alten“, zusammengefügten Einträge, werden aus den Distanzmatrixen gelöscht.

</p>

<th>

</th>

<th>Rose

</th>

<th>Tulpe

</th>

<th>MeMa

</th></tr>

<tr>

<th>Rose

</th>

<td>12

</td></tr>

<tr>

<th>Tulpe

</th>

<td>10

</td></tr>

<tr>

<th>MeMa

</th>

<td>0

</td></tr></tbody></table>

<p>Danach werden wieder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a0b6d651eaf432dbf1f106021c8bb499ae83fd1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.848ex; height:2.009ex;" alt="{\displaystyle r_{i}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{i,j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i,j}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0471da86bad57963868302a83a9decf6804d4197.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.189ex; height:2.843ex;" alt="{\displaystyle M_{i,j}}" loading="lazy"></span> berechnet, neu zusammengefügt und wieder von vorne angefangen. Dies wird solange wiederholt, bis nur noch zwei Taxa übrig bleiben, die dann schlussendlich verbunden werden.

</p><p>Das Ergebnis unseres Beispiels lässt sich wie folgt darstellen:

</p>

<th>additiver Baum</th>

<th>Ausgabe des Phylip Programms

</th></tr>

<tr>

<td>

<pre>Mensch Rose

\ /

\ 2 3 /

\ 9 /

-----------------

/ \

/ 1 1 \

/ \

Maus Tulpe

</pre>

</td>

<td>

<pre> +----Maus

 !

 ! +-------------Rose

1-----------------------------------------2

 ! +----Tulpe

 !

+--------Mensch

</pre>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Einordnung">Einordnung</h2></div>

<p>Neighbor-Joining gehört zu den expliziten Methoden. Dies bedeutet, dass bei der Berechnung der genetischen Distanzen unterschiedliche Evolutionsmodelle, also unterschiedliche Wahrscheinlichkeiten für Punktmutationen angenommen werden können. Die Richtigkeit dieser Stammbäume beruht auf der Annahme, dass die Veränderung der betrachteten Merkmale keine unbekannten Zwischenschritte enthält. Es wird also vereinfacht angenommen, dass „die Evolution keine Umwege geht“ (“minimum evolution”).

</p><p>Der Neighbor-Joining-Algorithmus berechnet den Stammbaum schrittweise und findet deshalb nicht zwangsläufig die optimale Baum-Topologie mit der geringsten Verzweigungslänge. Dies beruht auf seinem Konstruktionsprinzip, als <a href="Greedy-Algorithmus" title="Greedy-Algorithmus">Greedy-Algorithmus</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Im Gegensatz zu anderen Algorithmen berechnet dieser nicht alle möglichen Bäume und wählt zum Schluss die optimalen aus, sondern verwirft schon während des Verfahrens einige Rechenwege. Obwohl der Algorithmus suboptimal ist, wurde er ausführlich getestet und findet normalerweise einen Baum, der dem Optimum relativ nahekommt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Vorteile">Vorteile</h2></div>

<p>Der größte Vorteil dieses Verfahrens ist seine Geschwindigkeit. Man kann es auf gewaltige Datenmengen anwenden, selbst dort, wo andere Methoden der phylogenetischen Analyse wie <a href="Maximale_Sparsamkeit" class="mw-redirect" title="Maximale Sparsamkeit">maximum parsimony</a> und <a href="Maximum-Likelihood-Methode" title="Maximum-Likelihood-Methode">Maximum-Likelihood</a> nicht mehr durchführbar sind. Im Gegensatz zum UPGMA-Algorithmus (Unweighted Pair Group Method with Arithmetic mean) zur phylogenetischen Baumrekonstruktion nimmt Neighbor-Joining nicht an, dass die Entwicklung der Abstammungslinien mit derselben Rate (siehe auch <a href="Molekulare_Uhr" title="Molekulare Uhr">Molekulare Uhr</a>) stattfindet und erzeugt daher infolgedessen einen unbalancierten Baum.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>N. Saitou, M. Nei: <cite style="font-style:italic">The neighbor-joining method. A new method for reconstructing phylogenetic trees.</cite> In: <cite style="font-style:italic"><a href="Molecular_Biology_and_Evolution" title="Molecular Biology and Evolution">Molecular Biology and Evolution</a></cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>4</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>4</span>, 1. Juli 1987, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>406–425</span> (<a rel="nofollow" class="external text" href="http://mbe.oxfordjournals.org/content/4/4/406">oxfordjournals.org</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Neighbor-Joining-Algorithmus&rft.atitle=The+neighbor-joining+method.+A+new+method+for+reconstructing+phylogenetic+trees.&rft.au=N.+Saitou%2C+M.+Nei&rft.date=1987-07-01&rft.genre=journal&rft.issue=4&rft.jtitle=Molecular+Biology+and+Evolution&rft.pages=406-425&rft.volume=4" style="display:none"> </span></li>

<li>J. A. Studier, K. J. Keppler: <cite style="font-style:italic">A note on the neighbor-joining algorithm of Saitou and Nei</cite>. In: <cite style="font-style:italic">Molecular Biology and Evolution</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>5</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>6</span>, 1. November 1988, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>729–731</span>, <a class="external mw-magiclink-pmid" rel="nofollow" href="https://www.ncbi.nlm.nih.gov/pubmed/3221794?dopt=Abstract">PMID 3221794</a> (<a rel="nofollow" class="external text" href="http://mbe.oxfordjournals.org/content/5/6/729.full.pdf">mbe.oxfordjournals.org</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Neighbor-Joining-Algorithmus&rft.atitle=A+note+on+the+neighbor-joining+algorithm+of+Saitou+and+Nei&rft.au=J.+A.+Studier%2C+K.+J.+Keppler&rft.date=1988-11-01&rft.genre=journal&rft.issue=6&rft.jtitle=Molecular+Biology+and+Evolution&rft.pages=729-731&rft.pmid=3221794&rft.volume=5" style="display:none"> </span></li>

<li>Volker Knoop, Kai Müller: <cite style="font-style:italic">Gene und Stammbäume. Ein Handbuch zur molekularen Phylogenetik</cite>. 1. Auflage. Elsevier, Spektrum Akademischer Verlag, München / Heidelberg 2006, ISBN 3-8274-1642-6.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Neighbor-Joining-Algorithmus&rft.au=Volker+Knoop%2C+Kai+M%C3%BCller&rft.btitle=Gene+und+Stammb%C3%A4ume.+Ein+Handbuch+zur+molekularen+Phylogenetik&rft.date=2006&rft.edition=1.&rft.genre=book&rft.isbn=3827416426&rft.place=M%C3%BCnchen+%2F+Heidelberg&rft.pub=Elsevier%2C+Spektrum+Akademischer+Verlag" style="display:none"> </span></li>

<li>Olivier Gascuel, Mike Steel: <cite style="font-style:italic">Neighbor-Joining Revealed</cite>. In: <cite style="font-style:italic">Molecular Biology and Evolution</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>23</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>11</span>, 1. November 2006, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>1997–2000</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1093/molbev%2Fmsl072">10.1093/molbev/msl072</a></span>, <a class="external mw-magiclink-pmid" rel="nofollow" href="https://www.ncbi.nlm.nih.gov/pubmed/16877499?dopt=Abstract">PMID 16877499</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Neighbor-Joining-Algorithmus&rft.atitle=Neighbor-Joining+Revealed&rft.au=Olivier+Gascuel%2C+Mike+Steel&rft.date=2006-11-01&rft.doi=10.1093%2Fmolbev%2Fmsl072&rft.genre=journal&rft.issue=11&rft.jtitle=Molecular+Biology+and+Evolution&rft.pages=1997-2000&rft.pmid=16877499&rft.volume=23" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Quellen">Quellen</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">N. Saitou, M. Nei: <cite style="font-style:italic">The neighbor-joining method: a new method for reconstructing phylogenetic trees</cite>. In: <cite style="font-style:italic">Molecular Biology and Evolution</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>4</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>4</span>, Juli 1987, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220737-4038%22&key=cql">0737-4038</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>406–425</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1093/oxfordjournals.molbev.a040454">10.1093/oxfordjournals.molbev.a040454</a></span>, <a class="external mw-magiclink-pmid" rel="nofollow" href="https://www.ncbi.nlm.nih.gov/pubmed/3447015?dopt=Abstract">PMID 3447015</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Neighbor-Joining-Algorithmus&rft.atitle=The+neighbor-joining+method%3A+a+new+method+for+reconstructing+phylogenetic+trees&rft.au=N.+Saitou%2C+M.+Nei&rft.date=1987-07&rft.doi=10.1093%2Foxfordjournals.molbev.a040454&rft.genre=journal&rft.issn=0737-4038&rft.issue=4&rft.jtitle=Molecular+Biology+and+Evolution&rft.pages=406-425&rft.pmid=3447015&rft.volume=4" style="display:none"> </span></span>

</li>

<li id="cite_note-Algorithmus-2"><span class="mw-cite-backlink">↑ <sup><a href="#cite_ref-Algorithmus_2-0">a</a></sup> <sup><a href="#cite_ref-Algorithmus_2-1">b</a></sup></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://wwwmath.uni-muenster.de/statistik/lehre/SS12/SeminarMathBio/Vortraege/Phylo0.pdf"><i>3.1 neighbor-joining-Algorithmus</i></a> (PDF, S. 7).</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.icp.ucl.ac.be/~opperd/private/neighbor.html"><i>The Neighbor-Joining Method</i></a> auf icp.ucl.ac.be</span>

</li>

/* start https://de.wikipedia.org/ */

.mw-parser-output .webarchiv-memento a{color:inherit}

/* end https://de.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160916072208/http://www.stat.berkeley.edu/~terry/Classes/s246.2006/Week6/2neighbourJoining.pdf"><i>Neighbour Joining Method (Saitou and Nei, 1987)</i> Summary</a> (<span class="webarchiv-memento"><a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a></span> des <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><span class="dewiki-iconexternal"><a class="external text" href="https://redirecter.toolforge.org/?url=http%3A%2F%2Fwww.stat.berkeley.edu%2F%7Eterry%2FClasses%2Fs246.2006%2FWeek6%2F2neighbourJoining.pdf">Originals</a></span> vom 16. September 2016 im <i><a href="Internet_Archive" title="Internet Archive">Internet Archive</a></i>) <small class="archiv-bot"><span class="wp_boppel noviewer" aria-hidden="true" role="presentation"><span typeof="mw:File"><span title="i"></span></span></span> <b>Info:</b> Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.</small><span style="display:none"><a rel="nofollow" class="external text" href="http://IABotmemento.invalid/http://www.stat.berkeley.edu/~terry/Classes/s246.2006/Week6/2neighbourJoining.pdf">@1</a></span><span style="display:none"><a rel="nofollow" class="external text" href="http://www.stat.berkeley.edu/~terry/Classes/s246.2006/Week6/2neighbourJoining.pdf">@2</a></span><span style="display:none">Vorlage:Webachiv/IABot/www.stat.berkeley.edu</span> auf stat.berkeley.edu</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">Kord Eickmeyer, Peter Huggins, Lior Pachter, Ruriko Yoshida: <cite style="font-style:italic">On the optimality of the neighbor-joining algorithm</cite>. In: <cite style="font-style:italic">Algorithms for Molecular Biology (AMB)</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>3</span>, 30. April 2008, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%221748-7188%22&key=cql">1748-7188</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>5</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1186/1748-7188-3-5">10.1186/1748-7188-3-5</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Neighbor-Joining-Algorithmus&rft.atitle=On+the+optimality+of+the+neighbor-joining+algorithm&rft.au=Kord+Eickmeyer%2C+Peter+Huggins%2C+Lior+Pachter%2C+...&rft.date=2008-04-30&rft.doi=10.1186%2F1748-7188-3-5&rft.genre=journal&rft.issn=1748-7188&rft.jtitle=Algorithms+for+Molecular+Biology+%28AMB%29&rft.pages=5&rft.volume=3" style="display:none"> </span></span>

</li>

</ol>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20100311193350/http://www.sanger.ac.uk/resources/software/quicktree/">Quicktree – Eine Implementierung von Neighbour-Joining</a> (<span class="webarchiv-memento"><a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a></span> vom 11. März 2010 im <i><a href="Internet_Archive" title="Internet Archive">Internet Archive</a></i>)</li>

<li><a rel="nofollow" class="external text" href="http://evolution.genetics.washington.edu/phylip.html">Das PHYLIP-Paket</a></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-03-02" href="https://de.wikipedia.org/wiki/?title=Neighbor-Joining-Algorithmus&oldid=253831438">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>